package com.leecode;

import java.util.Map;
import java.util.Stack;

/**
 * 739. 每日温度
 *
 * 请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，
 * 至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
 * @formatter:off
 * 例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，
 * 你的输出应该是                   [1 ,  1,  4,  2,  1,  1,  0,  0]。
 * @formatter:on
 * 提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是
 * 在 [30, 100] 范围内的整数。
 *
 * 心得:悟了悟了,这题第一次让我知道,"了解数据结构"和"用好数据结构"是2码事!!
 * 当走到72的时候,要刚好可能更新到71
 * 当走到76的时候,要刚好可能更新到75,72
 * 这意味着:
 * 当到72时,有个"容器"装着"72之前要等待更新的节点"
 * 当到76时,有个"容器"装着"76之前要等待更新的节点"
 */
public class Leet739 {
	public static void main(String[] args) {
		new Leet739().dailyTemperatures(new int[]{73, 74, 75, 71, 69, 72, 76, 73});
	}

	/**
	 * 暴力(简单):1652ms,我决定优化,优化失败!!看答案,这数据结构玩得太6了吧?!!!
	 * 35%,71%
	 */
	public int[] dailyTemperatures2(int[] t) {
		int[] res = new int[t.length];

		Stack<Integer> stackDesc = new Stack();
		for (int a = 0; a < res.length; a++) {
			if (!stackDesc.isEmpty()) {
				while (true && !stackDesc.isEmpty()) {
					Integer peek = stackDesc.peek();
					if (t[a] > t[peek]) {
						Integer pop = stackDesc.pop();
						res[pop] = a - pop;
					}else{
						break;
					}
				}
			}
			stackDesc.push(a);
		}
		return res;
	}

	/**
	 * 98%,26%,?!!它没有用stack反而空间更少?
	 */
	public int[] dailyTemperatures(int[] T) {
		int[] res = new int[T.length];
		//从后面开始查找
		for (int i = res.length - 1; i >= 0; i--) {
			int j = i + 1;
			while (j < res.length) {
				if (T[j] > T[i]) {
					//如果找到就停止while循环
					res[i] = j - i;
					break;
				} else if (res[j] == 0) {//妙2:为0说明,后面不可能比当前大
					//如果没找到，并且res[j]==0。说明第j个元素后面没有
					//比第j个元素大的值，因为这一步是第i个元素大于第j个元素的值，
					//那么很明显这后面就更没有大于第i个元素的值。直接终止while循环。
					break;
				} else {//妙1:j+=属于跳跃式寻找,对比暴力挨个挨个,这优雅了
					//如果没找到，并且res[j]！=0说明第j个元素后面有比第j个元素大的值，
					//然后我们让j往后挪res[j]个单位，找到那个值，再和第i个元素比较
					j += res[j];
				}
			}
		}
		return res;
	}
}
